package com.javatest;

import edu.princeton.cs.algs4.StdOut;

import java.math.BigDecimal;
import java.math.BigInteger;

/**
 * @author LL
 * 递归算法
 * @create 2021-01-13 14:22
 */
public class Subject29 {

    /*
     * mystery(2, 25) 和 mystery(3, 11) 的返回值是多少？给定正整数 a 和 b，mystery(a,b)计算的结果是什么？
     * 将代码中的 + 替换为 * 并将 return 0 改为 return 1，然后回答相同的问题
     * */
    public static int mystery(int a ,int b){
        if (b == 0){
            return 0;
        }
        if (b%2 == 0){
            return mystery(a+a,b/2);
        }
        return mystery(a+a,b+2)+a;
    }

    /*
    * 计算机用这段程序在一个小时之内能够得到 F(N) 结果的最大 N 值是多少？
    * */
    public static long F1(int N){
        if(N == 0){
            return 0;
        }
        if(N == 1){
            return 1;
        }
        return F1(N-1) + F1(N-2);
    }
    //f(5)+f(4) ->f(4)+f(3) ->f(3)+f(2) ->f(2)+f(1) ->f(1)+f(0)-1
    //f(4)+f(3) ->f(3)+f(2) ->f(2)+f(1) ->f(1)+f(0)-1
    //f(3)+f(2) ->f(2)+f(1) ->f(1)+f(0)-1
    //f(2)+f(1) ->f(1)+f(0)-1
    //f(1)+f(0)-1
    //f(4)->f(3)->f(2)->f(1)-1
    //f(3)->f(1)-1
    //f(2)->f(1)-1

    //开发 F(N) 的一个更好的实现，用数组保存已经计算过的值。
    public static long F2(int N,long[] a){
        if(N == 0){
            return a[0] = 0;
        }
        if (N == 1){
            return a[1] = 1;
        }
        return a[N] = a[N-1]+(a[N-2]);
    }

    public static BigInteger F3(int N, BigInteger[] a){
        if(N == 0){
            return a[0] = BigInteger.valueOf(0);
        }
        if(N == 1){
            return a[1] = BigInteger.valueOf(1);
        }
        return a[N] = a[N-1].add(a[N-2]);
    }

    public static void main(String[] args) {
        BigInteger[] a = new BigInteger[100];
        for (int i = 0; i < 100; i++) {
            System.out.println(" " +F3(i,a));
        }
    }
}
